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)

0
votes
1answer
9 views

Finding when list of numbers reach periodicity given known values

I'm trying to figure out when numbers reach "periodicity" given known values. I've included an example below with image: I have known sizes (100, 75, and 50) that I would like to know how many times ...
2
votes
2answers
31 views

Probability of Boys and Girls in Row

Ten male friends and six female friends line up next to the bus stop in a row. Everyone just positions themselves at random. What is the probability that no two females are sitting next to each other? ...
1
vote
0answers
21 views

Proof Check: Number of elements of $\mathbb{F}_{p^{n}}$ of the form $a^{p}-a$ for some $a \in \mathbb{F}_{p^{n}}$.

Consider the map $\varphi:\mathbb{F}_{p^{n}} \rightarrow \mathbb{F}_{p^{n}}$ defined by $x \mapsto x^{p}-x$. Since $(a+b)^{p}= a^{p}+b^{p}$ for all $a,b \in \mathbb{F}_{p^{n}}$ we have that $\varphi$ ...
0
votes
0answers
27 views

Probability of a run of *n* or more of some color from a subset of colors drawing without replacement?

I recently asked the question "Probability of a run of k or more of a subset of categories in m multinoulli trials?" with a very nice answer from member Tad. I'm trying to extend a result from a ...
2
votes
0answers
37 views

Conjecture on a graded ring

Consider $B^{(n)}=\mathbb{F}_2[X_1,\dots,X_n]/(X_1^2,\dots,X_n^2)=\bigoplus_{i=0}^nB_i^{(n)}$, where $B_i^{(n)}$ is the space of homogeneous elements of degree $i$. Notice that ...
0
votes
0answers
4 views

Smallest near triangulation of the plane with an external face of size $4$ for which all interior vertices have minimum degree $5$?

Consider the near-triangulation $G$ with an external face of size $4$. What is the minimum number of interior vertices for which G has minimum degree 5 as to those vertices? The degrees of the $4$ ...
0
votes
1answer
22 views

Probability of an event if the sample space has identical elements

Suppose we have a box, with only one small hole. Suppose 10 distinct black balls and 20 distinct white balls are put in the box. Now, in a random draw of 1 ball, the probability that the ball drawn is ...
0
votes
1answer
38 views

Combinatorics: Can anyone give a hint?

I'm practicing combinatorics then I got stuck in this problem. Suppose that I have an unlimited supply of identical math books, history books and physics books. All are the same size, and I have room ...
4
votes
2answers
73 views

“Mastermind”-esque safe opening problem.

I read this interview question for a trading job and it seems quite difficult. What is the technique to solving it? You have a safe with six digits and a light. You can input a code, if you have ...
5
votes
2answers
67 views

Derivative of sum of powers

For fixed $n \geq 1$ and $p \in [0,1]$, is there a nice expression for the derivative of $\sum_{k=0}^n p^k (1-p)^{n-k}$ with respect to p?
1
vote
0answers
51 views

Minimum Cake Cutting for a Party

You are organizing a party. However, the number of guests to attend your party can be anything from $a_1$, $a_2$, $\ldots$, $a_n$, where the $a_i$'s are positive integers. You want to be ...
1
vote
2answers
47 views

Seating people in a circular table

It has always been an interesting question. If we have $10$ chairs and a round table, how many ways are there of seating $10$ people? I would say there are $10!$ ways to seat the people due to ...
3
votes
3answers
72 views

Prof Gould combinatorial identity 3.27 and its “cousin” formula

In the book on Combinatorial Identities of Prof Gould I found the identity 3.27 $$\sum_{k=0}^{\rho}\binom{2x+1}{2k+1}\binom{x-k}{\rho-k}=\frac{2x+1}{2\rho+1}\binom{x+\rho}{2\rho}2^{2\rho}$$ I now ...
-1
votes
2answers
30 views

Does the order in a circular arrangement matter?

I posted a question a while ago: Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs. My question here is: imagine a ...
2
votes
2answers
380 views

Stars and Bars vs PIE

I randomly made up this question so I could check: There are $3$ kids and $6$ gifts, how many ways to distribute so that each kid has at least one gift. Obviously, $**|**|**$ there are ...
2
votes
1answer
26 views

Degree of Polynomial in Centered Moments of Gamma$(n,1)$

I'm interested in the degree of the polynomial in $n$ of the expression for the $k$-th central moment $$ E((X_n - n)^k) $$ where $X_n$ is a Gamma$(n,1)$ random variable, that is, the sum of $n$ ...
1
vote
0answers
28 views

A question regarding matchings in bipartite graphs

Let $G=(V,E)$ be a graph with $V(G)=X\cup Y$, let $M_1$ be a matching that "covers" $X'\subseteq X$, and let $M_2$ be a matching that "covers" $Y'\subseteq Y$. Show that then there is a matching $M$ ...
5
votes
1answer
29 views

$n$-vertex $3$-edge-colored graphs with exactly $6$ automorphisms which preserve edge color classes, but permute the edge colors distinctly?

In each of these $3$-edge-colored graphs, there are exactly $6$ automorphisms which preserve the set of edge color classes: (These automorphisms don't necessarily map e.g. green edges to green ...
2
votes
1answer
41 views

how many strings are length 10 with 5 1's and 5 0's are there?

I used generating functions and got $A(x,y)=(x+y)^{10}$. Then I found the coefficient of the $x^5y^5$ and got $252$. Is that the correct answer?
6
votes
3answers
1k views

People sitting in a circle chewing gum

Ten people are sitting in a circle of ten chairs, chewing gum. Each person spits out his or her gum and places it either under his or her own chair or under an immediately adjacent chair. How many ...
0
votes
1answer
24 views

Basic doubt on Stirling numbers of Second Type

When learning Stirling numbers of Second Type, one simple doubt came to my mind and posting it here. The formula for Stirling numbers of Second Type is given as ...
1
vote
1answer
79 views

Permutations of the elements of $\mathbb Z_p$

Note Added by Robert Lewis, 2 August 2015 3:04 PM PST in an attempt to provide background, motivation, and other context for this engaging problem: This problem essentially asks for a method of ...
0
votes
2answers
31 views

Probability of picking up one ball of each color

A box contains 6 red, 4 white and 5 black balls. A person draws 4 balls from the box at random. Let P be the probability that among the balls drawn there is at least one ball of each color. Find 455 * ...
0
votes
1answer
47 views

How many combinations in 10x10x10 Rubik's cube?

I was wondering how many possible combinations there is in the cubes greater than 3x3x3 (4x4x4, 5x5x5, ..., 10x10x10)? We know that in 3x3x3 there are about 4,3 * 10^19 combinations, what about bigger ...
-3
votes
0answers
28 views
3
votes
2answers
46 views

Find the least $N$ so there is no square

Find the least positive integer $N$ such that the set of $1000$ consecutive integers beginning with $1000 \cdot N$ contains no square of an integer. Let $x^2$ appear before $1000N$ so: $(x+1)^2 ...
1
vote
2answers
23 views

How many sequences $(i_1,\ldots,i_d)$ of fixed length `d` of positive integers satisfy $\alpha\le i_1+\cdots+i_d\le\beta$?

Let $i\in\mathbb N^d$ and $|i|:=i_1+\cdots+i_n$. How can we calculate the cardinality of the set of all $i$ which satisfy $$\alpha\le|i|\le\beta$$ with given constants $\alpha,\beta\in\mathbb N$?
0
votes
0answers
23 views

Find the constant $k$

In a graph $G$ with $n$ vertices, let $T_1$ be the number of triangles one can make and $T_2$ be the numbers of tetrahedrons. Find the least constant $k$ such that $(T_2)^3\le k.(T_1)^4$.
0
votes
1answer
14 views

Inverse function for a sort of negative binomial distribution

I am trying to find the inverse function of $f(p) = \sum_{k=0}^{6}{\binom{6-H+k}{k} p^{7-H} (1-p)^k}$, where $0 \leq H \leq 6$ is a constant integer. Any ideas on how to do this? Or perhaps equally ...
0
votes
2answers
56 views

How many divisors of the combination of numbers?

Find the number of positive integers that are divisors of at least one of $A=10^{10}, B=15^7, C=18^{11}$ Instead of the PIE formula, I would like to use intuition. $10^{10}$ has $121$ divisors, ...
1
vote
1answer
37 views

How to use Principle of Inclusion-Exclusion here?

A while ago I posted a question: Coloring a Grid. Online, I seem to have stumbled upon a usage of PIE AOPS Wiki Solution AIME II #9. (1) Now, I have experience with PIE, but I do not see how to ...
1
vote
1answer
64 views

Expected Value of a Mosquito

A mosquito is walking at random on the nonnegative number line. She starts at $1$. When she is at $0$, she always takes a step $1$ unit to the right, but, from any positive position on the line, she ...
2
votes
1answer
25 views

Probability a card can win a trick with a trump suit

I'm working on the AI for a card game that uses a standard deck of 52 cards consisting of 13 cards in 4 (spades, clubs, diamonds, hearts) suits. Each player starts with 13 cards in their hand. ...
-1
votes
2answers
50 views

Circular table problem

I've looked other questions that might help solve my problem, but haven't found any people who've used my method to solve it. The problem goes like this: Suppose there are 7 men and 5 women, and they ...
6
votes
0answers
45 views

A combinatorial proof by tesselation of the plane.

Some days ago the following problem was posed in the site: given a set of $N$ points in the plane such that for each pair of points $p,q$ we have $\lVert p-q\rVert >1$, prove there is a subset of ...
2
votes
1answer
90 views

What is the number of set partitions of $\{1,1,2,2,3,3\}$?

It must be less than $B_6$ (where $B_6$ is the Bell number of $6$) since the elements are "duplicated". I would most appreciate a generating function that gives the number of set partitions of ...
2
votes
1answer
50 views

Counting number of bijections

The question is: Let $S = \{a,b,c,d\}$ and let $X : = \{f\colon S \to S \mid f \, \, \text{is bijective and } f(x) \ne x \, \, \text{for each}\, \, x \in S \}$. What is $|X|$? Is there a simple ...
2
votes
1answer
36 views

An easy (or not?) collection of proper sets .

Let $S$ be a finite set. We are given $k$ rows and in each row we have two subsets of $S$ which we call them $A_i$, $B_i$ (for the $i$th row, with $i\leq k$). $A_1$ and $B_1$ $A_2$ and $B_2$ . . ...
0
votes
2answers
39 views

Can we obtain the pair $(1,50)$ with these following operations?

It's a problem from some russian competition: We're given a card with two positive integers $(a,b)$ and we have tree machines which generate another card from the one we insert on it(I assume we ...
1
vote
2answers
70 views

Ways of coloring the $7\times1$ grid (with three colors)

Hints only please! A $7 \times 1$ board is completely covered by $m \times 1$ tiles without overlap; each tile may cover any number of consecutive squares, and each tile lies completely on the ...
-1
votes
1answer
20 views

How many structurally different latin squares of order 5 do exist?

I know the number of latin squares order 5 which start with 1 2 3 4 5 in the 1st row or column, that is 1344, but the greater part of that number consists of structural duplicates of each other. So, I ...
5
votes
0answers
40 views

Partition Of Graph's edges Into 3 Groups

Let $G = (V, E)$ be a bipartite graph. Prove that there is a partition of the set of edges $E$ into 3 disjoint parts: $E = E1 ∪ E2 ∪ E3$, $E1 ∩ E2 = E2 ∩ E3 = E3 ∩ E1 = ∅$, so that for ...
2
votes
1answer
40 views

How many 3 letter words can you form from 'EEAAP' [duplicate]

How many 3 letter words can you form from 'EEAAP' I think the answer is ${3\choose 3} * 3! + {2\choose 1} * 3 + {2\choose 1} *3=18$. Is this right? ${3\choose 3} * 3!$ = You pick all ...
3
votes
1answer
53 views

How many ways can you choose team of 5 people out of 7 men and 6 women in which there are at least 3 men?

I am confused by this question. I solved it by selecting 3 men first out of 7 men and then selecting 2 people out of 10 remaining person ( 4 men and 6 women ) . So my answer is C(7,3) * C(10,2) = ...
3
votes
1answer
44 views

Probability of the card following first ace being ace of spades or two of clubs

I am learning probability from Scheldon Ross' book. The question reads like this: A deck of 52 playing cards is shuffled, and the cards are turned up one at a time until the first ace appears. Is ...
0
votes
2answers
39 views

Probability and Combinatorics

I am trying to solve example 4.15 here but think the total number of outcomes in the solution is incorrect. This is my reasoning. We have 3 that qualify as best three, say BBB, and 2 as bad say OO. ...
0
votes
1answer
18 views

A succinct proof that the given graphs (red $K_n$ drawn cyclically, plus blue $2$-paths between closest vertices) have dihedral automorphism groups?

Take the complete graph $K_n$ ($n \geq 3$), on the red-colored vertex set $\mathbb{Z}_n$, say, and add a blue-colored $2$-path between each pair of vertices $v$, and $v+1$, we get a sequence of graphs ...
0
votes
1answer
40 views

Why is $^nC_r$ not equal to $ ^{n-k}C_{r-k}\times ^nC_k$?

Why is $^nC_r$ not equal to $ ^{n-k}C_{r-k}\times ^nC_k$ ? I know that by simplifying, we can obviously see that they are unequal. But consider this: Where am I going wrong?
2
votes
1answer
42 views

Probability of a run of *k* or more of a subset of categories in *m* multinoulli trials?

Given a multinoulli distribution of categories $(C_1,C_2,...,C_n)$ with associated probabilities $\left\{p_1,p_2,\ldots ,p_n\right\}$ with $\sum _{i=1}^n p_i=1$, is there a tractable way to get the ...
3
votes
2answers
52 views

Permutations minus Transpositions

I want a formula that allows me to find all the permutations in $S_n$ (which is the set of all the integers from 1 to $n$) which don't contain a transposition. Attempt: Lets call $g(n)$ the ...