For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

5
votes
1answer
85 views

Drawing previously undrawn cards from a deck

Suppose you have a deck of $y$ cards. First, randomly select $y-x$ distinct cards and sign the face of each, then shuffle all the cards back in to the deck. Proceed as follows: Draw a card. If it is ...
6
votes
1answer
62 views

Sequences where each number is a divisor of one less than the next

Let $N,k$ be fixed. Call a sequence of positive integers $a_1,a_2,\dots,a_k$ good if for each $i$, $a_i$ is a divisor of $a_{i-1}-1$. Consider the set $$S = \{a_i : a_1,\dots,a_k \text{ is a good ...
1
vote
1answer
604 views

Doubt on married couple seating arrangement problem

I am going through a solution of the following problem. "How many ways there are there to seat $n$ couples around a circular table with $2n$ chairs such that no couple sits next to each other, i.e., ...
4
votes
1answer
74 views

Order 5 People of team A, 5 People of team B and 5 People of team C in line

I want to calculate the probability that: each candidate stands next to at least one candidate from their group. At first I thought that subtract from $1$ the probability that each team stands ...
0
votes
1answer
103 views

Probability of specfici couples around a table

I am studying for my first actuary exam so these answers are for my review only and not for hw! To start: I am working with n married couples sitting around a round table. I want to know the ...
0
votes
1answer
143 views

How many cards of a single suit must be present in any set of n cards?

In a standard deck with 52 cards, 4 suits with 13 cards per suit. I feel like I may be looking at this question wrong from the angle of probabilities. How do I answer this?
1
vote
2answers
357 views

Prove that a complement graph of a tree is either connected or it's a union of an isolated vertex and a full graph

I managed to prove the second part - that a tree that is one vertex with n-1 degree and all the rest are connected to it - the complement graph of such tree is an isolated vertex and the rest of the ...
2
votes
2answers
161 views

Restricted number of k non-consecutive combinations out of n

Assume we need to choose $k$ numbers out of $[1...n]$ so no two numbers are consecutive. I know the number of such combinations is given by$\binom {n-k+1}{k}$. Assume the numbers are given by $r_1<...
2
votes
4answers
166 views

Permutation, Combinatorics

Stuck here : there are 100 objects labeled 1, 2,...100. They are arranged in all possible ways. How many arrangements are there in which object 28 comes before object 29. My approach : Consider ...
4
votes
3answers
204 views

Ways to sum to $n$ with $m$ integers that are $\le k$

Given three natural numbers $n$, $m$ and $k$, how many ways are there to write $n$ as the sum of $m$ natural numbers in the set $\{0, 1, \ldots, k\}$, where order does matter? I've seen the "Ways to ...
4
votes
1answer
161 views

A game with stones and finding the winning set

For a positive integer $n$, two players $A$ and $B$ play the following game : Given a pile of $s$ stones, the players take turn alternatively with $A$ going first. On each turn the player is allowed ...
2
votes
0answers
46 views

what does “modular” mean?

I find some similarity of the concept "modular set functions" to the cardinality function. But I don't see the cardinality function is also called "modular" or something else. I wonder what "modular" ...
4
votes
2answers
94 views

A combinatorial problem about number partition

Choose eight different numbers from one to twenty, prove that there must exist six different numbers such that $a+b+c=d+e+f$. Since $\binom{20}{8}$ is only $125970$, I can do it with brute force, but ...
3
votes
3answers
316 views

Binary sequence count of unique patterns

A binary sequence is a sequence of 1s and 0s, and there are $2^n$ such sequences of length $n$. Define the "pattern" as the number of consecutive $1$s in the sequence. For example, when $n=5$, the ...
0
votes
1answer
33 views

No minimal imperfect graph of order 200

Prove that there is no minimal imperfect graph of order 200, without using the Strong Perfect Graph Theorem.
1
vote
0answers
61 views

Is there a sharper bound than exponential for $\sum_{k\ge0}\frac{m!(k+n-m)!}{(k+n)!}\frac{s^k}{k!}$?

I am trying find a bound for an expression and I am getting something not quite as convenient as I hoped. Going through my calculations again I think that the only place I use a non sharp bound is ...
4
votes
0answers
80 views

Combinatorics and symmetric functions

(The actual questions in this posting are at the bottom.) Occasionally someone asks here how to show that every nonempty finite set has just as many subsets of odd cardinality as of even cardinality (...
1
vote
0answers
32 views

A set system generated by a closure operator?

Given a ground set $E$, and a matroid closure operator $\tau$ on $\mathcal P(E)$, we can define a set system $(E,F)$ with $$ F := \{X \in \mathcal P(E): \forall x \in X, x \notin \tau(X-\{x\}) \}$$ ...
2
votes
1answer
60 views

What is the realization of a graph in $\mathbb{R}^d$?

I am an undergraduate who has been overhearing students talking about realizations of graphs in $\mathbb{R}^d$, and I am curious to know what that means. To be honest, I don't even know what a '...
1
vote
1answer
41 views

Products of n exponential generating functions

So I am using exponential generating functions and have a question about taking the product of more than 2 exponential generating functions. I know that the product of 2 exponential generating ...
1
vote
1answer
50 views

constant length of blocks in partitions

Let's assume we have partitions $P_k$ of the set $\{1,...,n\}$. If we choose two partitions it can happen, that each of them has a constant length of its blocks, but that the intersection of these two ...
6
votes
1answer
1k views

A Proof of Correctness of Durstenfeld's Random Permutation Algorithm

Question: Does anyone have a precise mathematical proof of Durstenfeld's Algorithm? The first $O(n)$ shuffle or random permutation generator was published by Richard Durstenfeld in 1964. This ...
2
votes
1answer
146 views

Calculating probabilities around “overlapping” events.

Problem Suppose we have $n$ buckets, and we randomly select $p$ buckets to fill with water—a filled bucket may be chosen again. If we now randomly select $q$ buckets, how many of them will have water?...
0
votes
5answers
103 views

How to get from $\frac{n(n+1)}{2}$ to $n + \binom{n}{2}$?

How to get from $\frac{n(n+1)}{2}$ to $n + \binom{n}{2}$? I tried some transforming, but my main problem is that I don't know how to get to $n!$ and $(n-2)!$ from the original term.
4
votes
1answer
118 views

Prevent Alice from building a tower of height k

Alice and Bob take turns playing the tower of babel game, with Alice starting. In this game Alice has $m$ parcels of land. In each of Alice's turns she receives $n$ blocks and decides to distribute ...
18
votes
2answers
344 views

A game on a graph

Alice and Bob play a game on a complete graph ${G}$ with $2014$ vertices. They take moves in turn with Alice beginning. At each move Alice directs one undirected edge of $G$. At each move Bob chooses ...
0
votes
3answers
96 views

Permutation & Combination Doubt! [duplicate]

Given the letters A, A, B, B, C, D, E. How many different arrangements are possible that begins and ends with the letter "A"? I don't understand "user99680"'s explanation for arranging the two Bs in ...
2
votes
2answers
83 views

How many spanning trees (undirected) are there with exactly k leaf?

It occurred to me that in order to find how many of those are there, for every $k$ it's a bit different way of thinking, for example: for $k$ = 3 the answer is: $\binom{n}{3}(n-3)\frac{(n-2)!}{2!}$ ...
0
votes
2answers
66 views

Pigeonhole principle use

Let $P(x)$ be a property (not in the strict logical sense, this is only a combinatorial problem). What is the minimun number of elements that one should have to ensure that one have at least $k$ with ...
2
votes
1answer
212 views

Number of paths from A to B with no direction constraints

There's a fairly common problem finding paths which is usually stated something like this: Consider a grid that is 4 rows by 4 columns with the upper left corner named A and lower right corner ...
0
votes
1answer
38 views

How to get n from n-1

I know this question is probably trivial, but I'm having great difficulty with it for some reason. So, I want to solve for $p$: $n-1 \geq 2(n-p)$ I know that the answer is $n \leq 2p -1 =\frac{n+1}{...
0
votes
3answers
58 views

Triangle Probability Problem

I've just graduated as an undergraduate in statistics. My girlfriend presented a problem to me today after she was finished with a crochet project. She has created 80 crocheted triangles, each of ...
1
vote
3answers
62 views

How Many Hands Having 3 Cards of a Kind are There?

The conditions are as follows: Standard 52-card deck, 4 suits. 5-card hand. There must be three of a kind, but only this (i.e., no 4 of a kind or full house). I know this has been asked already, ...
0
votes
2answers
91 views

“SAT” probability

Problem: There are 3 Republicans and 2 Democrats on a Senate committee. if a 3-person subcommittee is to be formed from this committee, what is the probability of selecting 2 Republicans and 1 ...
10
votes
2answers
282 views

Stirling number

I am trying to evaluate the following finite sum: $$ \sum_{k=1}^{n}(-1)^{k}(k-1)!S(n-1, k-1)(\sum_{i=0}^{k-1}H_{i}), $$ where $S(n, k)$ are the Stirling's numbers of the second kind and $H_{i}$ ...
0
votes
1answer
292 views

SAT Probability and Counting

Given the letters A, A, B, B, C, D, E How many different arrangements are possible that begins and ends with the letter "A"? B,B,B,G,G Three boys and two girls shown above are lined up side by ...
2
votes
2answers
186 views

Hadamard Matrix

Prove that if $H$ is a (normalized) Hadamard matrix, then so is the matrix $\pmatrix{ H& H\\\ H& -H}$. I have been working on this and I know this statement is true. My book just simply says ...
0
votes
1answer
83 views

Counting nodes in a random tree

Suppose we have a random tree where the probability that a node has $n$ successors is given by $\delta(n)$. What is the distribution of the number of nodes at the $s$-th level deep in the tree, $N_s(n)...
0
votes
0answers
129 views

Relation between permutations and fourier transform?

i dont know if this is already addressed somewhere (searching around did not find sth). The motivation is to find a way to generate or produce permutations using concepts from continuous mathematics (...
1
vote
1answer
96 views

Number of “Unique effective” paths on a grid.

I know that for an NxM grid there are "M+N choose N" unique paths to "opposite" {corner to corner} vertices. I would like to know how many "effective unique paths" there are if I discount for ...
0
votes
1answer
77 views

Cutting a chessboard into domino pieces!

A friend of mine gave me this problem from a european olympiad: Suppose we have a $8\times8$ chessboard. Each edge has a number; the number of ways of dividing this chessboard into $1\times2$ and $2\...
0
votes
1answer
28 views

connected subsets of a set of vertices

I am struggeling with the following combinatorial problem: Suppose you have $n$ vertices $1,2,\ldots,n$. Successive numbers / vertices are considered as neighbours, e.g. the neighbours of 3 are 1 and ...
3
votes
4answers
7k views

Combination with repetition problem

So I have a question about a practice problem employing combination in which the repetition of elements is allowed, here it is: Determine the number of non-negative integer solutions to the ...
0
votes
2answers
920 views

How many combinations of three scoop cones are possibles?

An ice cream shop sells ice creams in five possible flavours. How many combinations of three scoop cones are possibles?[Note:The repetition of flavours is allowed but the order in which the flavours ...
2
votes
1answer
85 views

Conjugating a permutation

I am trying to see that two permutations are conjugate exactly when they have the same cycle decomposition. I fail to see that $$r(i_1,i_2,\dots,i_k)r^{−1}=(r(i_1),r(i_2),\dots,r(i_k))$$ Any thoughts ...
3
votes
2answers
89 views

Is there a nice characterization of these classes of functions on a set of $n$ elements?

I am looking at the set of all functions from $[n] \to [n]$, where $[n] = \{1,2,\dots,n\}$. Now, I consider two functions equivalent, if they are conjugates by some permutation, that is, they are the ...
8
votes
3answers
2k views

Edge coloring of the cube

We have a cube and we are coloring its edges. There are three colors available. We say that the two colorings are the same if one can obtain a second by turning cube and permuting colors. Find the ...
6
votes
3answers
354 views

Primitive binary necklaces

The problem/solution of counting the number of (primitive) necklaces is very well known. But what about results giving sufficient conditions for a given necklace be primitive? For example, in the ...
2
votes
1answer
379 views

Proving the Chinese Remainder Theorem using the Pigeonhole Principle

I am trying to prove a version of the Chinese Remainder Thoerem using the pigeonhole principle. The theorem that was provided: If n and m are relatively prime, then for all integers 0 ≤ a < n ...
0
votes
2answers
169 views

Could the birthday paradox be interpreted also about deaths?

Is the probability from the birthday paradox also true about deaths? If so, why? Or why not? I would think that it is also true about deaths, but it doesn't say so.